package com.foxzzz.dynamic.programming;

// ?
public class Solution152 {
    public static void main(String[] args) {
        System.out.println(new Solution152().maxProduct1(new int[]{7, -2, -4}));
        System.out.println(new Solution152().maxProduct1(new int[]{2, 3, -2, 4}));
        System.out.println(new Solution152().maxProduct1(new int[]{-2, 0, -1}));
        System.out.println(new Solution152().maxProduct1(new int[]{3, -1, 4}));
        System.out.println(new Solution152().maxProduct1(new int[]{2,-5,-2,-4,3}));
    }

    public int maxProduct1(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        //dp[x][y]
        int[][] dp = new int[nums.length][nums.length];
        dp[0][0] = nums[0];
        int max = dp[0][0];
        for (int i = 1; i < nums.length; i++) {
            for (int j = i; j > -1; j--) {
                if (i == j) {
                    dp[j][i] = nums[j];
                } else {
                    dp[j][i] = dp[j][i - 1] * nums[i];
                }
                max = max > dp[j][i] ? max : dp[j][i];
            }

        }
        return max;
    }

 /*   标签：动态规划
    遍历数组时计算当前最大值，不断更新
    令imax为当前最大值，则当前最大值为 imax = max(imax * nums[i], nums[i])
    由于存在负数，那么会导致最大的变最小的，最小的变最大的。因此还需要维护当前最小值imin，imin = min(imin * nums[i], nums[i])
    当负数出现时则imax与imin进行交换再进行下一步计算
    时间复杂度：O(n)O(n)
    代码
    极值和峰值动态规划
    */

        public int maxProduct(int[] nums) {
            int max = Integer.MIN_VALUE, imax = 1, imin = 1;
            for(int i=0; i<nums.length; i++){
                if(nums[i] < 0){
                    int tmp = imax;
                    imax = imin;
                    imin = tmp;
                }
                imax = Math.max(imax*nums[i], nums[i]);
                imin = Math.min(imin*nums[i], nums[i]);

                max = Math.max(max, imax);
            }
            return max;
        }



}
